﻿using System;

namespace Stack
{

    /// <summary>
    /// In computer science, a stack is a last in, first out (LIFO) abstract data type and linear data structure. A stack can have any abstract data type as 
    /// an element, but is characterized by two fundamental operations, called push and pop. The push operation adds a new item to the top of the stack, or 
    /// initializes the stack if it is empty. If the stack is full and does not contain enough space to accept the given item, the stack is then considered 
    /// to be in an overflow state. The pop operation removes an item from the top of the stack. A pop either reveals previously concealed items, or results
    /// in an empty stack, but if the stack is empty then it goes into underflow state (It means no items are present in stack to be removed). 
    /// 
    /// For more information visit:
    /// http://en.wikipedia.org/wiki/Stack_(abstract_data_type)
    /// http://www.ams.org/notices/200304/what-is.pdf
    /// http://www.ece.cmu.edu/~koopman/stack_computers/sec1_2.html
    /// http://www.c-sharpcorner.com/UploadFile/dsami/StackImplementationInCS11082005034453AM/StackImplementationInCS.aspx
    /// http://www.codeproject.com/Articles/17029/The-use-of-Stacks-in-C
    /// http://www.codeproject.com/Articles/33397/Multilevel-Undo-and-Redo-Implementation-in-C-Part
    /// </summary>
    public class Stack
    {
        private StackNode _top;
        private int _count;

        public int Count
        {
            get { return _count; }
            private set { _count = value; }
        }

        public Stack()
        {
            this._count = 0;
        }

        public void Push(object data)
        {
            StackNode node = new StackNode(data);

            if (_top == null)
            {
                this._top = node;
            }
            else
            {
                node.Next = this._top;
                this._top = node;
            }

            this._count++;
        }
        public object Pop()
        {
            object result = null;

            if (this._top != null)
            {
                result = this._top.Data;

                this._top = this._top.Next;
                this._count--;
            }

            return result;
        }
        public object Peek()
        {
            object result = null;

            if (this._top != null)
            {
                result = this._top.Data;
            }

            return result;
        }
        public void Clear()
        {
            this._top = null;
            this._count = 0;
        }
        public void Display()
        {
            StackNode node = this._top;

            while (node != null)
            {
                Console.WriteLine(string.Format(" {0}  ", "_ _"));
                Console.WriteLine(string.Format("| {0} |", node.Data));
                node = node.Next;
            }

            Console.ReadLine();
            Console.Clear();
        }
        public bool IsEmpty()
        {
            if (_count == 0)
                return true;
            else
                return false;
        }

        public void TowersOfHanoi(int n, Stack origin, Stack auxiliary, Stack destination)
        {
            if (n == 0)
            {
                return;
            }
            else
            {
                Console.WriteLine("Before move n= {0} from origin to destination", n);

                Console.WriteLine("Origin");
                origin.Display();
                Console.WriteLine();

                Console.WriteLine("Auxiliar");
                auxiliary.Display();
                Console.WriteLine();

                Console.WriteLine("Destination");
                destination.Display();
                Console.WriteLine();

                TowersOfHanoi(n - 1, origin, destination, auxiliary);

                object value = origin.Pop();
                destination.Push(value);
                Console.WriteLine("Moving {0} from origin to destination", value, origin, auxiliary);

                Console.WriteLine("After moving n={0} from origin to destination", n);

                Console.WriteLine("Origin");
                origin.Display();
                Console.WriteLine();

                Console.WriteLine("Auxiliar");
                auxiliary.Display();
                Console.WriteLine();

                Console.WriteLine("Destination");
                destination.Display();
                Console.WriteLine();

                Console.WriteLine("Before moving n={0} from auxiliar to origin", n - 1);
                TowersOfHanoi(n - 1, auxiliary, origin, destination);

                Console.WriteLine("After moving n={0} from auxiliar to origin", n);

                Console.WriteLine("Origin");
                origin.Display();
                Console.WriteLine();

                Console.WriteLine("Auxiliar");
                auxiliary.Display();
                Console.WriteLine();

                Console.WriteLine("Destination");
                destination.Display();
                Console.WriteLine();

            }
        }

        public void Sort()
        {
            Stack output = new Stack();
            SortAscendant(null, null);
        }

        private void SortAscendant(Stack output, object current)
        {
            if (this.IsEmpty() && current == null)
            {
                output.Display();
                return;
            }

            if (current == null)
                current = this.Pop();

            if (output.IsEmpty() || (int)output.Peek() < (int)current)
            {
                output.Push(current);
                SortAscendant(output, this.Pop());
            }
            else
            {
                this.Push(output.Pop());
                SortAscendant(output, current);
            }
        }
    }

    public class StackNode
    {
        public StackNode Next { get; set; }
        public object Data { get; set; }

        public StackNode()
        {
            this.Data = null;
            this.Next = null;
        }
        public StackNode(object data)
        {
            this.Data = data;
        }
    }
}
